<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
                      "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  <title>The Often Misunderstood GEP Instruction</title>
  <link rel="stylesheet" href="llvm.css" type="text/css">
  <style type="text/css">
    TABLE   { text-align: left; border: 1px solid black; border-collapse: collapse; margin: 0 0 0 0; }
  </style>
</head>
<body>

<div class="doc_title">
  The Often Misunderstood GEP Instruction
</div>

<ol>
  <li><a href="#intro">Introduction</a></li>
  <li><a href="#questions">The Questions</a>
  <ol>
    <li><a href="#extra_index">Why is the extra 0 index required?</a></li>
    <li><a href="#deref">What is dereferenced by GEP?</a></li>
    <li><a href="#firstptr">Why can you index through the first pointer but not
      subsequent ones?</a></li>
    <li><a href="#lead0">Why don't GEP x,0,0,1 and GEP x,1 alias? </a></li>
    <li><a href="#trail0">Why do GEP x,1,0,0 and GEP x,1 alias? </a></li>
  </ol></li>
  <li><a href="#summary">Summary</a></li>
</ol>

<div class="doc_author">
  <p>Written by: <a href="mailto:rspencer@reidspencer.com">Reid Spencer</a>.</p>
</div>


<!-- *********************************************************************** -->
<div class="doc_section"><a name="intro"><b>Introduction</b></a></div>
<!-- *********************************************************************** -->
<div class="doc_text"> 
  <p>This document seeks to dispel the mystery and confusion surrounding LLVM's
  GetElementPtr (GEP) instruction. Questions about the wiley GEP instruction are
  probably the most frequently occuring questions once a developer gets down to
  coding with LLVM. Here we lay out the sources of confusion and show that the
  GEP instruction is really quite simple.
  </p>
</div>

<!-- *********************************************************************** -->
<div class="doc_section"><a name="questions"><b>The Questions</b></a></div>
<!-- *********************************************************************** -->
<div class="doc_text">
  <p>When people are first confronted with the GEP instruction, they tend to
  relate it to known concepts from other programming paradigms, most notably C
  array indexing and field selection. However, GEP is a little different and
  this leads to the following questions; all of which are answered in the
  following sections.</p>
  <ol>
    <li><a href="#firstptr">What is the first index of the GEP instruction?</a>
    </li>
    <li><a href="#extra_index">Why is the extra 0 index required?</a></li>
    <li><a href="#deref">What is dereferenced by GEP?</a></li>
    <li><a href="#lead0">Why don't GEP x,0,0,1 and GEP x,1 alias? </a></li>
    <li><a href="#trail0">Why do GEP x,1,0,0 and GEP x,1 alias? </a></li>
  </ol>
</div>

<!-- *********************************************************************** -->
<div class="doc_subsection">
  <a name="firstptr"><b>What is the first index of the GEP instruction?</b></a>
</div>
<div class="doc_text">
  <p>Quick answer: The index stepping through the first operand.</p> 
  <p>The confusion with the first index usually arises from thinking about 
  the GetElementPtr instruction as if it was a C index operator. They aren't the
  same. For example, when we write, in "C":</p>

<div class="doc_code">
<pre>
AType *Foo;
...
X = &amp;Foo-&gt;F;
</pre>
</div>

  <p>it is natural to think that there is only one index, the selection of the
  field <tt>F</tt>.  However, in this example, <tt>Foo</tt> is a pointer. That 
  pointer must be indexed explicitly in LLVM. C, on the other hand, indexs
  through it transparently.  To arrive at the same address location as the C 
  code, you would provide the GEP instruction with two index operands. The 
  first operand indexes through the pointer; the second operand indexes the 
  field <tt>F</tt> of the structure, just as if you wrote:</p>

<div class="doc_code">
<pre>
X = &amp;Foo[0].F;
</pre>
</div>

  <p>Sometimes this question gets rephrased as:</p>
  <blockquote><p><i>Why is it okay to index through the first pointer, but 
      subsequent pointers won't be dereferenced?</i></p></blockquote> 
  <p>The answer is simply because memory does not have to be accessed to 
  perform the computation. The first operand to the GEP instruction must be a 
  value of a pointer type. The value of the pointer is provided directly to 
  the GEP instruction as an operand without any need for accessing memory. It 
  must, therefore be indexed and requires an index operand. Consider this 
  example:</p>

<div class="doc_code">
<pre>
struct munger_struct {
  int f1;
  int f2;
};
void munge(struct munger_struct *P) {
  P[0].f1 = P[1].f1 + P[2].f2;
}
...
munger_struct Array[3];
...
munge(Array);
</pre>
</div>

  <p>In this "C" example, the front end compiler (llvm-gcc) will generate three
  GEP instructions for the three indices through "P" in the assignment
  statement.  The function argument <tt>P</tt> will be the first operand of each
  of these GEP instructions.  The second operand indexes through that pointer.
  The third operand will be the field offset into the 
  <tt>struct munger_struct</tt> type,  for either the <tt>f1</tt> or 
  <tt>f2</tt> field. So, in LLVM assembly the <tt>munge</tt> function looks 
  like:</p>

<div class="doc_code">
<pre>
void %munge(%struct.munger_struct* %P) {
entry:
  %tmp = getelementptr %struct.munger_struct* %P, i32 1, i32 0
  %tmp = load i32* %tmp
  %tmp6 = getelementptr %struct.munger_struct* %P, i32 2, i32 1
  %tmp7 = load i32* %tmp6
  %tmp8 = add i32 %tmp7, %tmp
  %tmp9 = getelementptr %struct.munger_struct* %P, i32 0, i32 0
  store i32 %tmp8, i32* %tmp9
  ret void
}
</pre>
</div>

  <p>In each case the first operand is the pointer through which the GEP
  instruction starts. The same is true whether the first operand is an
  argument, allocated memory, or a global variable. </p>
  <p>To make this clear, let's consider a more obtuse example:</p>

<div class="doc_code">
<pre>
%MyVar = unintialized global i32
...
%idx1 = getelementptr i32* %MyVar, i64 0
%idx2 = getelementptr i32* %MyVar, i64 1
%idx3 = getelementptr i32* %MyVar, i64 2
</pre>
</div>

  <p>These GEP instructions are simply making address computations from the 
  base address of <tt>MyVar</tt>.  They compute, as follows (using C syntax):
  </p>

<div class="doc_code">
<pre>
idx1 = (char*) &amp;MyVar + 0
idx2 = (char*) &amp;MyVar + 4
idx3 = (char*) &amp;MyVar + 8
</pre>
</div>

  <p>Since the type <tt>i32</tt> is known to be four bytes long, the indices 
  0, 1 and 2 translate into memory offsets of 0, 4, and 8, respectively. No 
  memory is accessed to make these computations because the address of 
  <tt>%MyVar</tt> is passed directly to the GEP instructions.</p>
  <p>The obtuse part of this example is in the cases of <tt>%idx2</tt> and 
  <tt>%idx3</tt>. They result in the computation of addresses that point to
  memory past the end of the <tt>%MyVar</tt> global, which is only one
  <tt>i32</tt> long, not three <tt>i32</tt>s long.  While this is legal in LLVM,
  it is inadvisable because any load or store with the pointer that results 
  from these GEP instructions would produce undefined results.</p>
</div>

<!-- *********************************************************************** -->
<div class="doc_subsection">
  <a name="extra_index"><b>Why is the extra 0 index required?</b></a>
</div>
<!-- *********************************************************************** -->
<div class="doc_text">
  <p>Quick answer: there are no superfluous indices.</p>
  <p>This question arises most often when the GEP instruction is applied to a
  global variable which is always a pointer type. For example, consider
  this:</p>

<div class="doc_code">
<pre>
%MyStruct = uninitialized global { float*, i32 }
...
%idx = getelementptr { float*, i32 }* %MyStruct, i64 0, i32 1
</pre>
</div>

  <p>The GEP above yields an <tt>i32*</tt> by indexing the <tt>i32</tt> typed 
  field of the structure <tt>%MyStruct</tt>. When people first look at it, they 
  wonder why the <tt>i64 0</tt> index is needed. However, a closer inspection 
  of how globals and GEPs work reveals the need. Becoming aware of the following
  facts will dispell the confusion:</p>
  <ol>
    <li>The type of <tt>%MyStruct</tt> is <i>not</i> <tt>{ float*, i32 }</tt> 
    but rather <tt>{ float*, i32 }*</tt>. That is, <tt>%MyStruct</tt> is a 
    pointer to a structure containing a pointer to a <tt>float</tt> and an 
    <tt>i32</tt>.</li>
    <li>Point #1 is evidenced by noticing the type of the first operand of 
    the GEP instruction (<tt>%MyStruct</tt>) which is 
    <tt>{ float*, i32 }*</tt>.</li>
    <li>The first index, <tt>i64 0</tt> is required to step over the global
    variable <tt>%MyStruct</tt>.  Since the first argument to the GEP
    instruction must always be a value of pointer type, the first index 
    steps through that pointer. A value of 0 means 0 elements offset from that
    pointer.</li>
    <li>The second index, <tt>i32 1</tt> selects the second field of the
    structure (the <tt>i32</tt>). </li>
  </ol>
</div>

<!-- *********************************************************************** -->
<div class="doc_subsection">
  <a name="deref"><b>What is dereferenced by GEP?</b></a>
</div>
<div class="doc_text">
  <p>Quick answer: nothing.</p> 
  <p>The GetElementPtr instruction dereferences nothing. That is, it doesn't
  access memory in any way. That's what the Load and Store instructions are for.
  GEP is only involved in the computation of addresses. For example, consider 
  this:</p>

<div class="doc_code">
<pre>
%MyVar = uninitialized global { [40 x i32 ]* }
...
%idx = getelementptr { [40 x i32]* }* %MyVar, i64 0, i32 0, i64 0, i64 17
</pre>
</div>

  <p>In this example, we have a global variable, <tt>%MyVar</tt> that is a
  pointer to a structure containing a pointer to an array of 40 ints. The 
  GEP instruction seems to be accessing the 18th integer of the structure's
  array of ints. However, this is actually an illegal GEP instruction. It 
  won't compile. The reason is that the pointer in the structure <i>must</i>
  be dereferenced in order to index into the array of 40 ints. Since the 
  GEP instruction never accesses memory, it is illegal.</p>
  <p>In order to access the 18th integer in the array, you would need to do the
  following:</p>

<div class="doc_code">
<pre>
%idx = getelementptr { [40 x i32]* }* %, i64 0, i32 0
%arr = load [40 x i32]** %idx
%idx = getelementptr [40 x i32]* %arr, i64 0, i64 17
</pre>
</div>

  <p>In this case, we have to load the pointer in the structure with a load
  instruction before we can index into the array. If the example was changed 
  to:</p>

<div class="doc_code">
<pre>
%MyVar = uninitialized global { [40 x i32 ] }
...
%idx = getelementptr { [40 x i32] }*, i64 0, i32 0, i64 17
</pre>
</div>

  <p>then everything works fine. In this case, the structure does not contain a
  pointer and the GEP instruction can index through the global variable,
  into the first field of the structure and access the 18th <tt>i32</tt> in the 
  array there.</p>
</div>

<!-- *********************************************************************** -->
<div class="doc_subsection">
  <a name="lead0"><b>Why don't GEP x,0,0,1 and GEP x,1 alias?</b></a>
</div>
<div class="doc_text">
  <p>Quick Answer: They compute different address locations.</p>
  <p>If you look at the first indices in these GEP
  instructions you find that they are different (0 and 1), therefore the address
  computation diverges with that index. Consider this example:</p>

<div class="doc_code">
<pre>
%MyVar = global { [10 x i32 ] }
%idx1 = getlementptr { [10 x i32 ] }* %MyVar, i64 0, i32 0, i64 1
%idx2 = getlementptr { [10 x i32 ] }* %MyVar, i64 1
</pre>
</div>

  <p>In this example, <tt>idx1</tt> computes the address of the second integer
  in the array that is in the structure in %MyVar, that is <tt>MyVar+4</tt>. The 
  type of <tt>idx1</tt> is <tt>i32*</tt>. However, <tt>idx2</tt> computes the 
  address of <i>the next</i> structure after <tt>%MyVar</tt>. The type of 
  <tt>idx2</tt> is <tt>{ [10 x i32] }*</tt> and its value is equivalent 
  to <tt>MyVar + 40</tt> because it indexes past the ten 4-byte integers 
  in <tt>MyVar</tt>. Obviously, in such a situation, the pointers don't 
  alias.</p>
</div>

<!-- *********************************************************************** -->
<div class="doc_subsection">
  <a name="trail0"><b>Why do GEP x,1,0,0 and GEP x,1 alias?</b></a>
</div>
<div class="doc_text">
  <p>Quick Answer: They compute the same address location.</p>
  <p>These two GEP instructions will compute the same address because indexing
  through the 0th element does not change the address. However, it does change
  the type. Consider this example:</p>

<div class="doc_code">
<pre>
%MyVar = global { [10 x i32 ] }
%idx1 = getlementptr { [10 x i32 ] }* %MyVar, i64 1, i32 0, i64 0
%idx2 = getlementptr { [10 x i32 ] }* %MyVar, i64 1
</pre>
</div>

  <p>In this example, the value of <tt>%idx1</tt> is <tt>%MyVar+40</tt> and
  its type is <tt>i32*</tt>. The value of <tt>%idx2</tt> is also 
  <tt>MyVar+40</tt> but its type is <tt>{ [10 x i32] }*</tt>.</p>
</div>

<!-- *********************************************************************** -->
<div class="doc_section"><a name="summary"><b>Summary</b></a></div>
<!-- *********************************************************************** -->

<div class="doc_text">
  <p>In summary, here's some things to always remember about the GetElementPtr
  instruction:</p>
  <ol>
    <li>The GEP instruction never accesses memory, it only provides pointer
    computations.</li>
    <li>The first operand to the GEP instruction is always a pointer and it must
    be indexed.</li>
    <li>There are no superfluous indices for the GEP instruction.</li>
    <li>Trailing zero indices are superfluous for pointer aliasing, but not for
    the types of the pointers.</li>
    <li>Leading zero indices are not superfluous for pointer aliasing nor the
    types of the pointers.</li>
  </ol>
</div>

<!-- *********************************************************************** -->

<hr>
<address>
  <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
  src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
  <a href="http://validator.w3.org/check/referer"><img
  src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
  <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br/>
  Last modified: $Date: 2008-01-04 06:04:32 -0600 (Fri, 04 Jan 2008) $
</address>
</body>
</html>
